#include "mainwindow.h"
#include "ui_mainwindow.h"


MainWindow::MainWindow(QWidget *parent)
    : QMainWindow(parent)
    , ui(new Ui::MainWindow)
{

    ui->setupUi(this);

    QString str = ui->textEdit->toPlainText();
    connect(ui->pushButton, &QPushButton::clicked, this, &MainWindow::myfft);
    connect(ui->pushButton_2, &QPushButton::clicked, this, &MainWindow::mydft);

}

// 功能实现区域
// fft
void MainWindow::myfft(){

    QString str,str_m, str_run_time;
    int m, length;
    // 获取数列长度
    str_m = ui->textEdit_3->toPlainText();
    length = str_m.toInt();

    //length = 1<<m;
    std::complex<double>* c3 = new std::complex<double>[length]();

    str= ui->textEdit->toPlainText();
    //   字符转化为数组 并填数字
    forcin(str, c3);



    double run_time;
    _LARGE_INTEGER time_start;	//开始时间
    _LARGE_INTEGER time_over;	//结束时间
    double dqFreq;		//计时器频率
    LARGE_INTEGER f;	//计时器频率
    QueryPerformanceFrequency(&f);
    dqFreq=(double)f.QuadPart;
    QueryPerformanceCounter(&time_start);	//计时开始

    m = int(log(length)/log(2));
    //要计时的程序
    dit2(c3, m);


    QueryPerformanceCounter(&time_over);	//计时结束
    run_time = 1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;

    str_run_time = QString::number(run_time);

    ui->label_9->setNum(run_time);

    forout(c3, length);

    delete [] c3;
}


void MainWindow::mydft(){

    QString str_m, str_run_time;
    int m, length;

    // 获取数列长度length
    str_m = ui->textEdit_3->toPlainText();
    length = str_m.toInt();


    std::complex<double>* c3 = new std::complex<double>[length]();

    QString str;
    str = ui->textEdit->toPlainText();
    //   字符转化为数组 并填数字
    forcin(str,c3);


    double run_time;
    _LARGE_INTEGER time_start;	//开始时间
    _LARGE_INTEGER time_over;	//结束时间
    double dqFreq;		//计时器频率
    LARGE_INTEGER f;	//计时器频率
    QueryPerformanceFrequency(&f);
    dqFreq=(double)f.QuadPart;
    QueryPerformanceCounter(&time_start);	//计时开始

    m = int(log(length)/log(2));
    //要计时的程序
    dft(c3,m);

    QueryPerformanceCounter(&time_over);	//计时结束
    run_time = 1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    str_run_time = QString::number(run_time);
    ui->label_9->setNum(run_time);


    // 输出展示
    forout(c3, length);

    delete [] c3;
}



// fft实现
void MainWindow::dit2(std::complex<double>* Data, int M)
{
    int i, j, k, step, length,p;

    // 序列长度
    length = 1 << M;
    //倒位序输入
    //forinv(Data, length);
    Rader(Data, length);

 //  fft过程
// Log2N 就为层数 m w5
std::complex<double> wn, temp, deltawn;

    for (i = 1; i <= M; i++)
    {
        wn = 1;
        //  B
        step = 1 << (i - 1);

            for (j = 0; j <= step-1 ; j++)
            {
                p = (1 << (M - i) ) * j;
                // 本次蝶形运算跨越时间
                for (k = j+1; k <= length; k+=(1<<i) )
                {
                    deltawn = std::complex<double>(cos(2 * pi * p / length),
                        sin((-1) * 2.0 * pi * p/ length));

                    temp = Data[k-1] + Data[k + step-1] * deltawn;
                    Data[k + step-1] = Data[k-1] - Data[k + step-1] * deltawn;
                    Data[k-1] = temp;
                }
            }
      }
}

// dft
// 传统算法
void MainWindow::dft(std::complex<double>* Data, int Log2N)
{

    int i, j, length;
    std::complex<double> wn;
    // 相当于计算2的多少次方
    // (m>>2) < 1 相当于求最近的
    length = 1 << Log2N;

    std::complex<double>* temp = new std::complex<double>[length]();

    for (i = 0; i < length; i++){
        temp[i] = 0;
        for (j = 0; j < length; j++){
            wn = std::complex<double>(cos(2.0 * pi / length * i * j), sin((-1) * 2.0 * pi / length * i * j));
            temp[i] += Data[j] * wn;
        }
    }

    for(int i = 0;i < length;i++){
         Data[i] =  temp[i];
    }
   // Data = temp;

    delete[] temp;
}


//  用于从一串字符变成 数组

void MainWindow::forcin(QString str, std::complex<double>* Data){

    int num = 0;
    const char *p = str.toStdString().data();

    for (int i = 0; i < str.length(); i++)
        {
            if(i ==0 )
                Data[0] = std::atoi(p);
            if(str[i] == ' '){
               num++;
               Data[num] = std::atoi(p+i);
            }
        }
}

//  用于展示在edit处的输出
void MainWindow::forout(std::complex<double>* Data, int length){

    QString outpou;
     // 输出控制
    for (int mm = 0; mm < length; mm++) {

        //qDebug()<<Data[mm].real()<<"+"<<Data[mm].imag()<<"i"<<"  ";

        if(Data[mm].imag()>0){
            outpou = outpou + QString::number(Data[mm].real()) + "+";
            outpou = outpou + QString::number(Data[mm].imag()) + "i";
        }
        else if(Data[mm].imag() == 0.0){
             outpou = outpou + QString::number(Data[mm].real());
        }
        else{
            outpou = outpou + QString::number(Data[mm].real()) ;
            outpou = outpou + QString::number(Data[mm].imag()) + "i";
        }
        if(mm != length-1)
          outpou = outpou + "    ";

    }
    ui->textEdit_2->setText(outpou);
}




// 雷德算法倒序
void MainWindow::Rader(std::complex<double>* Data, int length){

     std::complex<double> temp1;
     int  nv2, nm1, j  = 0,i = 0;
         int k;
         nv2 = length/2;
         nm1 = length - 1;
         while( !(i >= nm1) ){
             if( !(i >= j) ) {
                 temp1 = Data[j]; Data[j] = Data[i]; Data[i] = temp1;
             }
             k = nv2;
             while( !(k > j) ){
                 j = j - k; k = k/2;
             }

             j = j + k; i = i + 1;
         }
}

// 倒位输入
void MainWindow::forinv(std::complex<double>* Data, int length){
    int i, j ,k;
    std::complex<double> temp1;

    double t;
    for (i = 0; i < length; i++)
    {
        k = i; j = 0; t = (log(length) / log(2.0));
        while ((t--) > 0)
        {
            j = j << 1; j |= (k & 1); k = k >> 1;
        }
        if (j > i)
        {
            temp1 = Data[i]; Data[i] = Data[j]; Data[j] = temp1;
        }
    }

}

MainWindow::~MainWindow()
{
    delete ui;
}




